package style.zcyLeetCode.a_0006_图;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * 生成图的工具类
 */
public class GraphGeneratorUtils {

    // 点
    public static class Node {
        public int value; // 数据项（点上的值）
        public int in;  // 入度
        public int out; // 出度
        public ArrayList<Node> nexts; // 当前点的直接邻居有哪些点
        public ArrayList<Edge> edges; // 当前点的直接连接的边（由当前点发散出去的边）

        public Node(int value) {
            this.value = value;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }

    // 边
    public static class Edge {
        public int weight; // 边的权值
        public Node from;  // 表示有向边
        public Node to;    // 表示有向边

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    // 图
    public static class Graph {
        public HashMap<Integer, Node> nodes;  // 点集
        public HashSet<Edge> edges;           // 边集

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }

    /**
     * 给定一个二维数组生成一个图
     * N * 3 的矩阵
     * [weight、from节点上面的value、to节点上面的value]
     */
    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (Integer[] integers : matrix) {
            Integer weight = integers[0];
            Integer from = integers[1];
            Integer to = integers[2];
            // 当点没出现过
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            // 点全部出现
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode); // 新边
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}
